#include <bits/stdc++.h>
#define ru_(i,l,r) for(int i=(l);i<=(r);i++)
#define ru(i,l,r) for(int i=(l);i<(r);i++)
#define rd_(i,r,l) for(int i=(r);i>=(l);i--)
#define rd(i,r,l) for(int i=(r);i>(l);i--)
#define ll long long
#define pli pair<ll,int>
#define s1 first
#define s2 second

using namespace std;
#ifdef LOCAL
#include 'algo/debug.h'
#else
#define debug(...)
#endif
//ios::sync_with_stdio(0); cin.tie(0);

struct a{
    int main(){
        int t;cin>>t;
        while(t--){
            int a,b; cin>>a>>b;
            cout<<a+b<<endl;
        }
    }
};
struct b{ // struct int[] 最大长度1e5
    int a[200000];
    int main(){
        int t,n;cin>>t;
        while(t--){
            cin>>n;
            if(n==1)cout<<"1"<<endl;
            else if(n==2)cout<<"1 2"<<endl;
            else{
                int c=4; fill(a,a+n,0);
                a[0]=2,a[n/2]=1,a[n-1]=3;
                ru(i,0,n) if(a[i]==0) a[i]=c++;
                ru(i,0,n) printf("%d%c",a[i],(i==n-1)?'\n':' ');
            }
        }
    }
};
struct c{
    int main(){
        int i,t,n,c[200000];cin>>t;
        while(t--){
            cin>>n; ru(i,0,n)cin>>c[i];
            int allneg=1;ru(i,0,n)allneg&=(c[i]<0);
            if(allneg)cout<<*max_element(c,c+n)<<endl;
            else{
                long long int ans1=0,ans2=0;
                ru(i,0,n){
                    if(i&1)ans1+=max(c[i],0);
                    else ans2+=max(c[i],0);
                }
                cout<<max(ans1,ans2)<<endl;
            }
        }
        return 0;
    }
};
struct d{
    char s[1000001];
    int main(){
        int i,t,n;cin>>t;
        while(t--){
            cin>>n; int c=1; while((n%c)==0)c++;
            ru(i,0,n)s[i]='a'+(i%c);
            s[n]='\0'; cout<<s<<endl;
        }
        return 0;
    }
};
struct e{
    vector<pair<int,int>> adjList[4000];
    int colour[4000], bad=0;
    int dfs(int u,int c){
        if(colour[u]!=-1){
            if(colour[u]!=c)bad=1;
            return 0;
        }
        colour[u]=c;
        for(auto [v,e]: adjList[u]) dfs(v,c^e);
        return 0;
    }
    int main(){
        int x1,y1,x2,y2;
        int t;cin>>t;
        while(t--){
            int n,m,k; cin>>n>>m>>k;
            ru(i,0,k){
                cin>>x1>>y1>>x2>>y2;
                x1--,y1--,x2--,y2--;
                adjList[min(x1,x2)].push_back(make_pair(n+min(y1,y2),(x1+y1!=x2+y2)));
                adjList[n+min(y1,y2)].push_back(make_pair(min(x1,x2),(x1+y1!=x2+y2)));
            }
            fill(colour,colour+n+m,-1),bad=0;
            ru(i,0,n+m) if(colour[i]==-1)dfs(i,0);
            printf(bad?"no\n":"yes\n");
//            cout<<(bad?"no\n":"yes\n");
            ru(i,0,n+m) adjList[i].clear();
        }
    }
};
struct f{
    int a[20000], b[20000], l[20000], r[20000];
    set<pair<int,int>> S;
    int main(){
        int t;cin>>t;
        while(t--){
            int n,c; cin>>n>>c;
            for(int i=0;i<n;i++) cin>>a[i];
            if(c>=0){
                sort(a,a+n);
                for(int i=0;i<n;i++)printf("%d%c",a[i],(i==n-1)?'\n':' ');
                continue;
            }
            sort(a,a+n,greater<int>());
            b[0]=a[0];
            for(int i=0;i<n;i++)l[i]=(i+n-1)%n, r[i]=(i+1)%n;
            for(int i=2;i<n-1;i++){
                if(a[l[i]]-a[r[i]]<=-c) S.insert(make_pair(a[i],i));
            }
            for(int i=1;i<n;i++){
                int u;
                auto it=S.lower_bound(make_pair(b[i-1]+c,0));
                if(it==S.end()) u=r[0];
                else u=it->second, S.erase(it);
                b[i]=a[u];
                int x=l[u],y=r[u];
                r[x]=y,l[y]=x;
                S.erase(make_pair(a[x],x)), S.erase(make_pair(a[y],y));
                if((x!=0)&&(l[x]!=0)&&(r[x]!=0)&&(a[l[x]]-a[r[x]]<=-c)) S.insert(make_pair(a[x],x));
                if((y!=0)&&(l[y]!=0)&&(r[y]!=0)&&(a[l[y]]-a[l[y]]<=-c)) S.insert(make_pair(a[y],y));
            }
            for(int i=0;i<n;i++) printf("%d%c",b[i],(i==n-1)?'\n':' ');
        }
    }
};

struct g{
    typedef long long int LLI;
    typedef vector<pair<int,int> > vpii;
#define mp make_pair
#define pb push_back

    vpii adjList[100];
    LLI d[10000];
    int parent[100][17],parenti[100],depth[10000];
    int doDFS(int u,int p,int d) {
        parent[u][0] = p,depth[u] = d;
        for (auto [v,i]: adjList[u]) {
            if (v != p) parenti[v] = i,doDFS(v,u,d+1);
        }
        return 0;
    }
    int logn;
    int lca(int u,int v) {
        int i;
        if (depth[u] < depth[v]) swap(u,v);
        for (i = logn-1; i >= 0; i--) {
            if ((parent[u][i] != -1) && (depth[parent[u][i]] >= depth[v])) u = parent[u][i];
        }
        if (u == v) return u;
        for (i = logn-1; i >= 0; i--) {
            if (parent[u][i] != parent[v][i]) u = parent[u][i],v = parent[v][i];
        }
        return parent[u][0];
    }
    int lcas[10000],bit[10000];
    LLI ans[10000],w[10000];
    int main() {
        int i;
        int n,u,v;
        scanf("%d",&n);
        for (i = 0; i < n-1; i++) {
            scanf("%d %d",&u,&v);
            u--,v--;
            adjList[u].pb(mp(v,i));
            adjList[v].pb(mp(u,i));
        }
        for (i = 0; i < n-1; i++) scanf("%lld",&d[i]);

        int j;
        doDFS(0,-1,0);
        for (i = 1; (1 << i) < n; i++) {
            for (j = 0; j < n; j++) {
                if (parent[j][i-1] != -1) parent[j][i] = parent[parent[j][i-1]][i-1];
                else parent[j][i] = -1;
            }
        }
        logn = i;
        for (i = 0; i < n-1; i++) lcas[i] = lca(i,i+1);

        for (i = 0; i < 57; i++) {
            bit[0] = 0;
            for (j = 0; j < n-1; j++) bit[j+1] = bit[j]^(d[j] & 1);
            for (j = 0; j < n-1; j++) d[j] = (d[j]-bit[j]-bit[j+1]+2*bit[lcas[j]])/2;
            for (j = 0; j < n; j++) ans[j] |= ((LLI) bit[j] << i);
        }
        for (i = 0; i < n-1; i++) {
            if (d[i] != 0) {
                printf("-1\n");
                return 0;
            }
        }
        for (i = 1; i < n; i++) {
            w[parenti[i]] = ans[i]-ans[parent[i][0]];
            if (w[parenti[i]] <= 0) {
                printf("-1\n");
                return 0;
            }
        }
        for (i = 0; i < n-1; i++) printf("%lld\n",w[i]);
        return 0;
    }
};
struct h{
#define MOD 998244353
#define LLI long long int
    int parent[30000],siz[30000];
    int find(int n) {
        if (parent[n] != n) parent[n] = find(parent[n]);
        return parent[n];
    }
    int queries[6000][3],ans[60000];
    int fact[30000],invfact[30000],invn[30000];
    int inv(int n) {
        int e = MOD-2,r = 1;
        while (e > 0) {
            if (e & 1) r = ((LLI) r*n) % MOD;
            e >>= 1;
            n = ((LLI) n*n) % MOD;
        }
        return r;
    }
    int main() {
        int i;
        int n,x,y,bad = 1e9;
        int num[3];
        scanf("%d",&n);
        for (i = 0; i < n; i++) parent[i] = i,siz[i] = 1;
        num[0] = 0,num[1] = n,num[2] = 0;
        for (i = 0; i < n; i++) {
            scanf("%d %d",&x,&y);
            x--,y--;
            if (find(x) != find(y)) {
                num[siz[find(x)] % 3]--;
                num[siz[find(y)] % 3]--;
                siz[find(y)] += siz[find(x)];
                parent[find(x)] = find(y);
                num[siz[find(y)] % 3]++;
            }
            else if ((siz[find(x)] % 3) == 0) num[0]--;
            else if (bad == 1e9) bad = i;
            copy(num,num+3,queries[i]);
        }

        fact[0] = 1;
        for (i = 1; i < n; i++) fact[i] = ((LLI) i*fact[i-1]) % MOD;
        invfact[n-1] = inv(fact[n-1]);
        for (i = n-2; i >= 0; i--) invfact[i] = ((LLI) (i+1)*invfact[i+1]) % MOD;
        for (i = 1; i < n; i++) invn[i] = ((LLI) invfact[i]*fact[i-1]) % MOD;

        int m = n;
        while (num[1]+num[2] > 0) {
            int a = (num[1] > 0) ? 1:2;
            num[a]--;
            int b = (num[1] > 0) ? 1:2;
            num[b]--;
            num[(a+b) % 3]++;
            copy(num,num+3,queries[m++]);
        }
        x = 1,y = 1;
        int u = 1,v = 8;
        auto f = [&]() {
            assert(x > 0);
            int nu = (((v-(((LLI) (y+1)*(x+y+1)) % MOD)*u) % MOD)*invn[x]) % MOD;
            int nv = ((((LLI) x*(x+y+2)) % MOD)*nu+(LLI) (y+2)*v) % MOD;
            x--,y += 2,u = nu,v = nv;
            if (u < 0) u += MOD;
            if (v < 0) v += MOD;
        };
        auto g = [&]() {
            assert(y > 0);
            int nu = (((v-(((LLI) (x+1)*(x+y+1)) % MOD)*u) % MOD)*invn[y]) % MOD;
            int nv = ((((LLI) y*(x+y+2)) % MOD)*nu+(LLI) (x+2)*v) % MOD;
            x += 2,y--,u = nu,v = nv;
            if (u < 0) u += MOD;
            if (v < 0) v += MOD;
        };
        for (i = m-1; i >= 0; i--) {
            int a = queries[i][1],b = queries[i][2],c = queries[i][0];
            if ((a == 0) && (b == 0)) ans[i] = 1;
            else if ((a == x) && (b == y)) ans[i] = u;
            else if ((a == x-1) && (b == y+2)) f(),ans[i] = u;
            else if ((a == x+2) && (b == y-1)) g(),ans[i] = u;
            else if ((a == x+1) && (b == y+1)) {
                if (x > 0) f(),g(),ans[i] = u;
                else g(),f(),ans[i] = u;
            }
            else assert(0);
            ans[i] = ((LLI) ans[i]*fact[a+b+c]) % MOD;
            ans[i] = ((LLI) ans[i]*invfact[a+b]) % MOD;
        }
        for (i = 0; i < n; i++) printf("%d\n",(i >= bad) ? 0:ans[i]);

        return 0;
    }
};

int main(){
//    a a;a.main();
//    b b; b.main();
//    c c;c.main();

//    e e;e.main();
//    f f;f.main();
//    g g;g.main();
    h h;h.main();

}